一、GraphWave [2018]

《Learning Structural Node Embeddings via Diffusion Wavelets》

1. 图中的结构角色发现（structural role discovery ）侧重于识别具有相似拓扑网络邻域的节点，这些节点可能位于网络中相距遥远的区域。如下图所示，尽管节点 $a$$a$ 和 $b$$b$ 在图中相距甚远，但它们具有相似的结构角色（ structural role ）。直观而言，具有相似结构角色的节点在网络中执行相似的功能，例如公司社交网络中的 manager 、或者细胞分子网络中的酶。这种节点相似性的定义与传统的定义非常不同。传统的节点相似性定义假设图上一定程度的平滑性（ smoothness ），因此网络中距离较近的节点是相似的。这种关于节点结构角色的信息可用于各种任务，包括作为机器学习问题的输入、识别系统中的关键节点（如社交网络中的核心 “影响者”、传染图中的关键 hub）。

   

   当在离散空间上定义节点的结构角色时，这些结构角色对应于局部网络邻域（local network neighborhood）的不同拓扑，例如链条上的节点、星形的中心、两个簇之间的 bridge 。然而，这种离散角色必须预定义（pre-defined ），并且需要领域内的专业知识和人工探查图结构。一种用于识别结构相似性的更强大、更鲁棒的方法是，以无监督的方式学习每个节点 $v$$v$ 的结构 embedding 向量 ${\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec x}_v$ 。这启发了根据拓扑 embedding 的邻近性对结构相似性（structural similarity ）的自然定义：对于任意 $ϵ>0$$\epsilon \gt 0$，如果 $\text{dist}({\overrightarrow{\mathbf{x}}}_a,{\overrightarrow{\mathbf{x}}}_b)\le ϵ$$\text{dist}(\mathbf{\vec x}_a,\mathbf{\vec x}_b) \le \epsilon$ 则节点 $a,b$$a,b$ 被定义为 ϵ-structurally similar的。因此这种方法必须引入适当的embedding 方法以及一个合适的距离函数dist() 。

   虽然已有几种方法来学习图中节点的结构 embedding （structural embedding） ，但是现有方法对拓扑中的小扰动极为敏感，并且缺乏对所学到 embedding 特性的数学理解。此外，它们通常需要人工标记拓扑特征（《RolX: structural role extraction & mining in large graphs》）、依赖于不可扩展non-scalable 的启发式方法（《struc2vec: Learning node representations from structural identity》）、和/或返回单个相似性得分而不是多维结构 embedding （《Scalable and axiomatic ranking of network role similarity》，《Axiomatic ranking of network role similarity》）。

   在论文 《Learning Structural Node Embeddings via Diffusion Wavelets》 中，作者通过开发 GraphWave 来解决图上的结构学习（structure learning） 问题。基于图信号处理（graph signal processing ）技术，论文的方法基于以节点为中心的谱图小波的扩散（ diffusion of a spectral graph wavelet ），从而为每个节点学习多维连续的结构 embedding 。直观而言，每个节点在图上传播一个能量单位（ a unit of energy），并根据网络对该探针（probe ）的响应来刻画其邻域拓扑（ neighboring topology ）。论文正式证明了这个小波（wavelet ）的系数与图拓扑性质直接相关。因此，这些系数包含恢复结构相似节点的所有必要信息，而无需对特征进行显式地人工标记（ hand-labeling ）。

   然而，根据设计，小波在图上是局部的。因此如果两个节点相距较远，则它们之间的小波是无法进行比较的。这时需要为每对节点指定一个一对一的映射，从而使得一对节点之间的小波可以进行直接比较，如计算每对顶点的小波之间的相关系数或者计算 $L_2$$L_2$ 距离。这种节点对之间的一一映射计算量太大，因此是难以实现的。所以这些小波方法从未被用于学习结构embedding 。

   为了克服这一挑战，论文提出了一种新的方法从而将小波视为图上的概率分布。这样，结构信息包含在 “diffusion 如何在网络上传播”，而不是“diffusion 在网络上传播到哪里”。为了提供 embedding ，论文使用经验特性函数 （empirical characteristic function ）来嵌入这些小波分布（ wavelet distribution ）。经验特性函数的优点是它们捕获给定分布的所有矩（包括高阶矩）。正如论文在数学上证明的那样，这允许 GraphWave 对局部边结构（ local edge structure ）中的小扰动具有鲁棒性。GraphWave 的计算复杂度在 edge 数量上是线性的，因此可以扩展到大型（稀疏的）网络。最后，论文在真实数据集和人工合成数据集上，将 GraphWave 与几个 SOTA 基准进行比较，获得了 137% 的提升。论文还展示了GraphWave 如何成为图中结构 embedding 的有效工具。

   论文的主要贡献如下：

   • 论文通过将谱图小波（spectral graph wavelet） 视为概率分布，并使用经验特性函数来刻画这个分布，从而提出了谱图小波的新用途。

   • 论文利用这些洞察开发了一种可扩展的方法 GraphWave，该方法基于图中结构相似性来学习节点 embedding，并优于现有的 SOTA 基准方法。

   • 论文在数学上证明 GraphWave 准确地恢复了结构相似（structurally similar ）和结构等价（structurally equivalent） 的节点。

2. 相关工作：关于挖掘相似结构角色节点的先前工作通常依赖于节点的显式特征。在基于这种 heuristic representation 计算节点相似性之前，这些方法生成每个节点的局部拓扑属性（local topological property ）的详尽列表，例如节点（ degree）、节点参与的三角形数量、k-clique 数量、PageRank 得分。这些方法中的一个值得注意的例子是 RolX，它是一种基于矩阵分解的方法，旨在使用递归的特征抽取（ recursive feature extraction ）从而将节点的软聚类（ soft　clustering ）恢复为预定数量的 $K$$K$ 个不同角色。类似地，struc2vec 使用启发式方法构建基于拓扑指标 （topological metric ）的 multilayer graph ，并在图上模拟随机游走从而捕获结构信息。相比之下，我们的方法不依赖于启发式（因为我们在数学上证明了我们方法的有效性），并且不需要显式的人工特征工程、或人工超参数调优。

   最近的神经表示学习（ neural representation learning ）方法（structure2vec、neural fingerprint、graph convolutional network: GCN、message passing network 等等）是相关的研究方向。然而，这些 graph embedding 方法不适用于我们的 setting，因为它们解决了监督的图分类任务、和/或嵌入了整个 graph。相比之下，我们的方法是无监督的，并且仅嵌入单个节点。

   另一类相关工作是 graph diffusion kernel （《Diffusion maps》），该方法已被用于各种图建模任务。然而，据我们所知，我们的论文是第一个应用 graph diffusion kernel 来确定图中结构角色的论文。 kernel 已被证明可以有效地捕获几何属性，并已成功用于图像处理社区中的形状检测（shape detection） 。然而，与形状匹配（shape-matching ）问题相比，GraphWave 将这些 kernel 视为真实世界的图上的概率分布。这是因为我们考虑的图是高度不规则的（与欧式图 Euclidean graph 和流形图 manifold graph 相反）。因此，传统的小波方法通常分析以规则和可预测的模式发生的、特定节点上的节点扩散（ node diffusion ），这种方法并不适用于我们的场景。相反，GraphWave 刻画了扩散的形状（diffusion shape），而不是扩散发生的特定节点。这一关键洞察使我们能够发现结构 embedding，从而进一步发现结构相似的节点。

1.1 模型

1. 给定无向图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$，其中 $\mathcal{V}$$\mathcal V$ 为节点集合，$\mathcal{E}$$\mathcal E$ 为边集合，$N$$N$ 为节点数量。令邻接矩阵为 $\mathbf{A}$$\mathbf A$ ，它是二元的或者带权重的。定义度矩阵 $\mathbf{D}$$\mathbf D$ ，其中 $D_{i,i}=\sum _j{A}_{i,j}$$D_{i,i} = \sum_j A_{i,j}$ 。

   节点的结构　embedding 问题为：对于每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ ，我们希望在一个连续的多维空间中学得一个 embedding 来表示它的结构角色（structural role ）。我们将这个问题构建为基于谱图小波（spectral graph wavelet） 的无监督学习问题，并开发了一种称为 GraphWave 的方法。该方法从数学上保证了所学到结构 embedding 的最优性能。

1.1.1 谱图小波

1. 令 $\mathbf{L}=\mathbf{D}-\mathbf{A}$$\mathbf L = \mathbf D-\mathbf A$ 为未归一化的拉普拉斯矩阵，令 $\mathbf{U}$$\mathbf U$ 为 $\mathbf{L}$$\mathbf L$ 的特征向量（eigen　vector ）组成的特征矩阵，则有：

   $$\mathbf{L}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^T$$

   其中 $\mathbf{\Lambda }=\text{diag}({\lambda }_1,\cdots ,{\lambda }_N)$$\mathbf\Lambda = \text{diag}(\lambda_1,\cdots,\lambda_N)$ ，${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_N$$\lambda_1\le \lambda_2\le\cdots\le \lambda_{N}$ 为 $\mathbf{L}$$\mathbf L$ 的特征值（eigen　value ）。

   图拉普拉斯矩阵的性质：

   • 图拉普拉斯矩阵是半正定矩阵，因此有 $0\le {\lambda }_1\le \cdots \le {\lambda }_N$$0\le \lambda_1\le\cdots\le \lambda_N$ 。

   • ${\lambda }_1=0$$\lambda_1 = 0$ ，因为拉普拉斯矩阵每一行的和均为零。

   • 特征值中 0 出现的次数就是图连通区域的个数。对于单连通图，有 $0={\lambda }_1<{\lambda }_2\le \cdots \le {\lambda }_N$$0=\lambda_1\lt \lambda_2\le\cdots\le \lambda_N$ 。

   • 最小非零特征值是图的代数连通度，通常记作 ${\lambda }_2$$\lambda_2$ 。

   令 $g_s$$g_s$ 为一个scaling 参数为 $s$$s$ 的滤波器核 （filter kernel），这里我们采用热核（heat kernel） $g_s(\lambda )=e^{-\lambda s}$$g_s(\lambda) = e^{-\lambda s}$ ，但是我们的结论适用于任何类型的 scaling wavelet 。另外，这里我们假设 $s$$s$ 是给定的，后续会讨论如何选择一个合适的 $s$$s$ 值。

   图信号处理（graph signal processing ）将与 $g_s$$g_s$ 相关的谱图小波（spectral graph wavelet） 定义为：以顶点 $v$$v$ 为中心的狄拉克信号的频域响应。因此谱图小波 ${\mathrm{\Psi }}_v$$\Psi_v$ 定义为：

   $${\mathrm{\Psi }}_v=\mathbf{U}\text{diag}(g_s({\lambda }_1),\cdots ,g_s({\lambda }_n)){\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\delta }}_v\in {\mathbb{R}}^N$$

   其中 ${\overrightarrow{\delta }}_v$$\vec\delta_v$ 是顶点 $v$$v$ 的 one-hot 向量：顶点 $v$$v$ 对应的位置为1，其它位置为0 。因此节点 $v$$v$ 的第 $m$$m$ 个小波系数为 ${\mathrm{\Psi }}_{m,v}=\sum _{l=1}^N{g}_s({\lambda }_l)U_{m,l}{U}_{v,l}$$\Psi_{m,v} = \sum_{l=1}^N g_s(\lambda_l)U_{m,l}U_{v,l}$ 。

   谱图矩阵 $\mathbf{\Psi }=\mathbf{U}\text{diag}(g_s({\lambda }_1),\cdots ,g_s({\lambda }_N)){\mathbf{U}}^{\mathrm{\top }}\in {\mathbb{R}}^{N\times N}$$\mathbf \Psi = \mathbf U \text{diag}(g_s(\lambda_1),\cdots,g_s(\lambda_{N}))\mathbf U^\top\in \mathbb R^{N\times N}$ ，它的第 $v$$v$ 列就是 ${\mathrm{\Psi }}_v$$\Psi_v$ ，它的第 $v$$v$ 列第 $m$$m$ 行就是 ${\mathrm{\Psi }}_{m,v}$$\Psi_{m,v}$ 。

   ${\mathrm{\Psi }}_{m,v}$$\;\Psi_{m,v}$ 的物理意义为：节点 $v$$v$ 处的狄拉克信号在节点 $m$$m$ 处的响应。并且该系数是对称的，即 ${\mathrm{\Psi }}_{m,v}={\mathrm{\Psi }}_{v,m}$$\Psi_{m,v}= \Psi_{v,m}$ 。

2. 可以看到在谱图小波中，核 $g_s$$g_s$ 调制（ modulate ）了特征谱（eigen　spectrum ），使得响应信号位于空域的局部区域以及频域的局部区域。如果我们将拉普拉斯矩阵和信号系统中的 ”时域-频域“ 进行类比，则发现：

   • 较小特征值对应的特征向量携带变化缓慢的信号，从而鼓励邻居节点共享相似的信息。

   • 较大特征值对应的特征向量携带迅速变化的信号，从而使得邻域节点之间区别较大。

   因此低通滤波器核（low-pass filter kernel） $g_s$$g_s$ 可以看作是一种调制算子（modulation operator） ，它降低了较高的特征值并在图中平滑了信号的变化。

1.1.2 GraphWave

1. 我们首先描述 GraphWave 算法，然后对其进行分析。对于每个节点 $v$$v$ ，GraphWave 返回表示其结构embedding 的一个 2d 维的向量 ${\overrightarrow{\mathbf{x}}}_v\in {\mathbb{R}}^{2d}$$\mathbf{\vec x}_v\in \mathbb R^{2d}$ ，使得局部网络结构相似的节点拥有相似的 embedding 。

2. 算法中，我们首先应用谱图小波来获取每个顶点的 diffusion pattern， 然后收集到矩阵 $\mathbf{\Psi }=\mathbf{U}{g}_s(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}\in {\mathbb{R}}^{N\times N}$$\mathbf \Psi = \mathbf Ug_s(\mathbf \Lambda)\mathbf U^\top\in \mathbb R^{N\times N}$ 中，其中第 $v$$v$ 列的列向量是以节点 $v$$v$ 为中心的 heat kernel 产生的谱图小波。

   现有的工作主要研究将小波系数视为scaling 参数 $s$$s$ 的函数，而这里我们将小波系数视为局部网络结构的函数：小波系数随着节点 $v$$v$ 的局部网络结构的变化而变化。具体而言，每个小波系数都由节点来标识，并且都有深刻的物理意义：${\mathrm{\Psi }}_{m,v}$$\Psi_{m,v}$ 表示节点 $v$$v$ 从节点 $m$$m$ 接收到的能量的大小（由于对称性，它也表示节点 $m$$m$ 从节点 $v$$v$ 接收到的能量的大小）。我们将小波系数视为概率分布，并通过经验特性函数来刻画该分布。我们将证明：具有相似网络邻域结构的节点 $u$$u$ 和 $v$$v$ 将具有相似的谱图小波系数分布 ${\mathrm{\Psi }}_u$$\Psi_u$ 和 ${\mathrm{\Psi }}_v$$\Psi_v$ 。这是一个关键的洞察，这使得 GraphWave 可以通过谱图小波学习节点的结构 embedding 。

   更准确地说，我们通过计算每个节点的小波系数 ${\mathrm{\Psi }}_v$$\Psi_v$ 的特性函数，并将其在 $d$$d$ 个均匀间隔的空间点采样，从而将谱图小波系数分布（spectral graph wavelet coefficient distribution ）嵌入到 $2d$$2d$ 维的空间。概率分布 $X$$X$ 的特性函数定义为：

   $${\varphi }_X(t)=\mathbb{E}[e^{itX}],t\in \mathbb{R}$$

   它完全刻画了分布 $X$$X$ ，因为它捕获了关于分布 $X$$X$ 的所有矩的信息。将它进行泰勒展开得到：

   $$\begin{array}{c}{\varphi }_X(t)=\mathbb{E}(1+\frac{itX}{1}+\frac{(it{)}^2{X}^2}{2!}+\cdots +\frac{(it{)}^n{X}^2}{n!}+\cdots )\\ =1+\underset{\text{一阶矩}}{\underbrace{\frac{it\mathbb{E}[X]}{1}}}+\underset{\text{二阶矩}}{\underbrace{\frac{(it{)}^2\mathbb{E}[X^2]}{2!}}}+\cdots +\underset{\text{n阶矩}}{\underbrace{\frac{(it{)}^n\mathbb{E}[X^n]}{n!}}}+\cdots \end{array}$$

   给定节点 $v$$v$ 和 scale s ，${\mathrm{\Psi }}_v$$\Psi_v$ 的经验特性函数定义为：

   $${\varphi }_v(t)=\frac{1}{N}\sum _{m=1}^N{e}^{it\times {\mathrm{\Psi }}_{m,v}}$$

   理论上我们需要计算足够多的点来描述 ${\varphi }_v(t)$$\phi_v(t)$，但是这里我们采样了 $d$$d$ 个均匀间隔的点，即 $\{t_1,\cdots ,t_d\}$$\{t_1,\cdots,t_d\}$ 。最终得到：

   $${\overrightarrow{\mathbf{x}}}_v={(\text{Re}({\varphi }_v(t_1)),\text{Im}({\varphi }_v(t_1)),\cdots ,\text{Re}({\varphi }_v(t_d)),\text{Im}({\varphi }_v(t_d)))}^{\mathrm{\top }}\in {\mathbb{R}}^{2d}$$

   注意到我们在经验特性函数 ${\varphi }_v(t)$$\phi_v(t)$ 上均匀采样了 $d$$d$ 个点，这创建了一个大小为 $2d$$2d$ 的 embedding，因此embedding 的维度和图的大小无关。

   GraphWave 核心思想：节点空域的局部结构相似性问题，转变为频域的小波相似性问题。它并没有采用最优化过程来优化某个代价函数，因此也没有梯度下降法来迭代求解。

3. GraphWave 算法：

   • 输入：

     • 图$\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$

     • scale 参数 $s$$s$

     • $d$$d$ 个均匀分布的采样点 $\{t_1,\cdots ,t_d\}$$\{t_1,\cdots,t_d\}$

   • 输出：节点的结构embedding 向量 ${\{{\overrightarrow{\mathbf{x}}}_v\in {\mathbb{R}}^{2d}\}}_{v\in \mathcal{V}}$$\left\{\mathbf{\vec x}_v\in \mathbb R^{2d}\right\}_{v\in \mathcal V}$

   • 算法步骤：

     • 计算拉普拉斯矩阵 $\mathbf{L}$$\mathbf L$ ，并进行特征分解：$\mathbf{L}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\mathrm{\top }}$$\mathbf L = \mathbf U\mathbf\Lambda \mathbf U^\top$ 。

     • 计算图谱小波 $\mathbf{\Psi }=\mathbf{U}{g}_s(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}$$\mathbf \Psi = \mathbf Ug_s(\mathbf \Lambda)\mathbf U^\top$ 。

     • 对 $t\in \{t_1,\cdots ,t_d\}$$t\in \{t_1,\cdots,t_d\}$，计算 $\varphi (t)\in {\mathbb{R}}^N$$\phi(t)\in \mathbb R^{N}$ 为 $e^{it\mathbf{\Psi }}$$e^{it\mathbf \Psi}$ 的 column-wise 逐列均值。对于节点 $v\in \mathcal{V}$$v\in \mathcal V$ ，将 ${\varphi }_v(t)$$\phi_v(t)$ 的实部和虚部分配给 ${\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec x}_v$ ，其中 ${\varphi }_v(t)$$\phi_v(t)$ 为 $\varphi (t)$$\phi(t)$ 的第 $v$$v$ 个元素。

       每个节点拼接 $d$$d$ 个实部和 $d$$d$ 个虚部，则得到一个 2d 维的向量。

4. 结构 embedding 之间的距离：GraphWave 的输出为图中每个节点的结构embedding 。我们可以将结构embedding之间的距离定义为 $L_2$$L_2$ 距离，即节点 $u$$u$ 和 $v$$v$ 之间的结构距离定义为：

   $$\text{dist}(u,v)=||{\overrightarrow{\mathbf{x}}}_u-{\overrightarrow{\mathbf{x}}}_v|{|}_2$$

   根据函数的定义，这相当于在小波系数分布上比较不同阶次的矩。

5. scaling 参数：scaling 参数 $s$$s$ 确定每个节点 $v$$v$ 周围的网络邻域的半径。

   • 较小的 $s$$s$ 会使用较小半径的邻域来确定节点的结构 embedding 。

   • 较大的 $s$$s$ 会使得扩散过程在网络上传播得更远，从而导致使用较大半径的邻域来确定节点的结构 embedding 。

   GraphWave 还可以采用 $s$$s$ 的不同取值来集成多尺度结构embedding ，这是通过拼接 $J$$J$ 个不同的 embedding ${\overrightarrow{\mathbf{x}}}_v^{(s_j)},j=1,2,\cdots ,J$$\mathbf{\vec x}_v^{(s_j)},j=1,2,\cdots,J$ 来实现的，每个embedding 都和一个scale $s_j$$s_j$ 相关，其中 $s_j\in [s_{min},s_{max}]$$s_j\in [s_\min,s_\max]$ 。我们接下来提供一个理论上的方法来找到合适的 $s_{min},s_{max}$$s_\min,s_\max$ 。

   在多尺度版本的 GraphWave 中，最终节点 $v$$v$ 聚合的结构embedding 为：

   $${\overrightarrow{\mathbf{x}}}_v={(\text{Re}({\varphi }_v^{(s_j)}(t_i)),\text{Im}({\varphi }_v^{(s_j)}(t_i)))}_{t_i,s_j}^{\mathrm{\top }}$$

6. 计算复杂度：我们使用切比雪夫多项式来计算 $\mathbf{\Psi }$$\mathbf \Psi$，拉普拉斯算子的每个幂具有 $O(|\mathcal{E}|)$$O(|\mathcal E|)$ 的计算成本，从而产生 $O(K\times |\mathcal{E}|)$$O(K\times |\mathcal E|)$ 的整体计算复杂度，其中 $K$$K$ 表示切比雪夫多项式逼近的阶数。因此 GraphWave 的整体计算复杂度是 edge 数量的线性的，这使得 GraphWave 可以扩展到大型稀疏网络。

1.1.3 理论分析

1. 这里我们为基于谱图小波的模型提供了理论动机。我们首先通过理论分析表明：谱图小波系数刻画了局部网络领域的拓扑结构。然后我们理论上证明：结构等价/相似的节点具有几乎相等/近似的embedding ，从而为 GraphWave 的最优性能提供了数学保证。

2. 谱图小波和网络结构：我们首先建立节点 $v$$v$ 的谱图小波和节点 $v$$v$ 的局部网络结构之间的关系。具体而言，我们证明了小波系数${\mathrm{\Psi }}_{m,v}$$\Psi_{ m,v }$ 提供了节点 $v$$v$ 和节点 $m$$m$ 之间网络连通性（network connectivity ）的度量。

   由于图拉普拉斯算子的谱是离散的，并且位于区间 $[0,{\lambda }_N]$$[0,\lambda_{N}]$ 之间，根据 Stone-Weierstrass 定理可知：核 $g_s$$g_s$ 在区间 $[0,{\lambda }_N]$$[0,\lambda_{N}]$ 上可以通过一个多项式来逼近。记这个多项式为 $P$$P$ ，则这个多项式逼近是紧的 tight，其误差是一致有界的 uniformaly bounded 。即：

   $$\mathrm{\forall }ϵ>0,\mathrm{\exists }P:P(\lambda )=\sum _{k=0}^K{\alpha }_k{\lambda }^k,s.t.|g_s(\lambda )-P(\lambda )|\le ϵ\mathrm{\forall }\lambda \in [0,{\lambda }_N]$$

   其中 $K$$K$ 为多项式逼近的阶数，${\alpha }_k$$\alpha_k$ 为多项式系数，$r(\lambda )=g_s(\lambda )-P(\lambda )$$r(\lambda) = g_s(\lambda) - P(\lambda)$ 为残差。

   我们可以将顶点 $v$$v$ 的谱图小波以多项式逼近的形式重写为：

   $${\mathrm{\Psi }}_v=\left(\sum _{k=0}^K{\alpha }_k{\mathbf{L}}^k\right){\overrightarrow{\delta }}_v+\mathbf{U}r(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\delta }}_v$$

   由于 $\mathbf{U}$$\mathbf U$ 是单位正交矩阵，$r(\lambda )$$r(\lambda)$ 是一致有界的，因此我们可以通过Cauchy-Schwartz 不等式将等式右侧的第二项进行不等式变换 ：

   $$\begin{array}{c}{|{\overrightarrow{\delta }}_m\cdot (\mathbf{U}r(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\delta }}_v)|}^2={(\sum _{j=1}^{N}r({\lambda }_j)U_{v,j}{U}_{m,j})}^2\\ \le (\sum _{j=1}^N|r({\lambda }_j){|}^2{U}_{v,j}^2)\left(\sum _{j=1}^N{U}_{m,j}^2\right)\le {ϵ}^2\end{array}$$

   其中等式左边为 $(\mathbf{U}r(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\delta }}_v)$$\left(\mathbf Ur(\mathbf\Lambda)\mathbf U^\top\vec \delta_v\right)$ 的第 $m$$m$ 个元素，$\sum _{j=1}^N{U}_{m,j}^2=1$$\sum_{j=1}^{N}U_{m,j}^2 = 1$ （因为 $\mathbf{U}$$\mathbf U$ 为单位正交矩阵）， 以及：

   $$\sum _{j=1}^N|r({\lambda }_j){|}^2{U}_{v,j}^2\le \sum _{j=1}^N{ϵ}^2{U}_{v,j}^2={ϵ}^2$$

   因此每个小波 ${\mathrm{\Psi }}_v\simeq \left(\sum _{k=0}^K{\alpha }_k{\mathbf{L}}^k\right){\overrightarrow{\delta }}_v$$\Psi_v\simeq \left(\sum_{k=0}^K\alpha_k\mathbf L^k\right)\vec \delta_v$ 可以由一个 $K$$K$ 阶多项式逼近，该多项式捕获了有关顶点 $v$$v$ 的 $K$$K$ 阶邻域信息。这表明谱图小波主要受到顶点的局部拓扑结构影响，因此小波包含了生成顶点结构embedding 所必须的信息。

3. 结构等价节点的 embedding ：然后我们证明局部邻域结构相同的顶点具有相似的 embedding 。假设顶点 $u$$u$ 和 $v$$v$ 的 $K$$K$ 阶邻域相同，其中 $K$$K$ 是一个小于图的直径的整数。这意味着顶点 $u$$u$ 和 $v$$v$ 在结构上是等价的。我们现在证明 $u$$u$ 和 $v$$v$ 在 GraphWave 中具有 ϵ-structurally similar embedding 。

   我们首先将 $g_s$$g_s$ 根据泰勒公式在零点展开到 $K$$K$ 阶：

   $$g(s)=e^{-\lambda s}\simeq P(\lambda ,s)=\sum _{k=0}^K(-1{)}^k\frac{(s\lambda {)}^k}{k!}$$

   然后对于每个特征值 $\lambda$$\lambda$，我们使用Taylor-Lagrange 等式来确保存在 $c_{\lambda }\in [0,s]$$c_\lambda \in [0,s]$ ，使得：

   $$|r(\lambda )|=|g(s)-P(\lambda ,s)|=\frac{(\lambda s{)}^{K+1}}{(K+1)!}{e}^{(-\lambda c_{\lambda })}\le \frac{(\lambda s{)}^{K+1}}{(K+1)!}$$

   如果我们选择 $s$$s$ 使得满足：

   $$s\le \frac{((K+1)!ϵ{)}^{1/(K+1)}}{{\lambda }_2}$$

   则可以保证绝对残差 $|r(\lambda )|\le ϵ$$|r(\lambda)|\le \epsilon$ 对于任意 $\lambda$$\lambda$ 成立。这里 $ϵ$$\epsilon$ 是一个参数，可以根据结构等效的顶点的embedding 期望的接近程度来指定，因此也称作 ϵ-structurally similar 。另外 $s$$s$ 越小则可以选择 $ϵ$$\epsilon$ 更小，使得上界越紧。

   注意，这里采用 ${\lambda }_2$$\lambda_2$ 是因为最小的特征值 ${\lambda }_1=0$$\lambda_1 = 0$ 。

   由于顶点 $u$$u$ 和 $v$$v$ 的邻域是相同的，因此存在一个one-to-one 映射 $\pi$$\pi$ ，它将 $u$$u$ 的 $K$$K$ 阶邻域 ${\mathcal{N}}_K(u)$$\mathcal N_K(u)$ 映射到 $v$$v$ 的 $K$$K$ 阶邻域 ${\mathcal{N}}_K(v)$$\mathcal N_K(v)$ ，使得 ${\mathcal{N}}_K(v)=\pi ({\mathcal{N}}_k(u))$$\mathcal N_K(v) = \pi(\mathcal N_k(u))$ 。通过随机映射剩余的顶点（$u$$u$ 的 $K$$K$ 阶邻域以外的顶点），我们将 $\pi$$\pi$ 作用到整个图 $\mathcal{G}$$\mathcal G$ 上。

   利用图拉普拉斯矩阵的 $K$$K$ 阶多项式近似，我们有：

   $$\begin{array}{c}|{\mathrm{\Psi }}_{m,u}-{\mathrm{\Psi }}_{\pi (m),v}|=|{\overrightarrow{\delta }}_m\cdot (\mathbf{U}(P(\mathbf{\Lambda })+r(\mathbf{\Lambda })){\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\delta }}_u)-{\overrightarrow{\delta }}_{\pi (m)}\cdot (\mathbf{U}(P(\mathbf{\Lambda })+r(\mathbf{\Lambda })){\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\delta }}_v)|\\ \le |(\mathbf{U}P(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}{)}_{m,u}-(\mathbf{U}P(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}{)}_{\pi (m),v}|+|(\mathbf{U}r(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}{)}_{m,u}|+|(\mathbf{U}r(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}{)}_{\pi (m),v}|\end{array}$$

   • 考虑第二行的第一项。由于顶点 $u$$u$ 和 $v$$v$ 的 $K$$K$ 阶邻域是等价的，以及拉普拉斯算子 K 阶幂的局部性（表示路径为 K 的路径）则有：

     $$\{\begin{array}{ll}(\sum _{k=0}^K{\alpha }_k{\mathbf{L}}^k{)}_{m,u}=(\sum _{k=0}^K{\alpha }_k{\mathbf{L}}^k{)}_{\pi (m),v},& \mathrm{\forall }m\in {\mathcal{N}}_K(u)\\ (\sum _{k=0}^K{\alpha }_k{\mathbf{L}}^k{)}_{m,u}=(\sum _{k=0}^K{\alpha }_k{\mathbf{L}}^k{)}_{\pi (m),v}=0,& \mathrm{\forall }m\notin {\mathcal{N}}_K(u)\end{array}$$

     因此这一项可以约掉。

     第二个等式为零，这是因为 $m$$m$ 不在节点 $u$$u$ 的 $K$$K$ 阶邻域内，因此也就不存在从节点 $m$$m$ 到 $u$$u$ 的、长度为 $K$$K$ 的路径。

   • 考虑第二行的第二项、第三项。使用前面的残差分析可以得到它们都有一个一致的上界 $ϵ$$\epsilon$，因此有：

     $$|{\mathrm{\Psi }}_{m,u}-{\mathrm{\Psi }}_{\pi (m),v}|\le 2ϵ$$

     即：${\mathrm{\Psi }}_u$$\Psi_u$ 中的每个小波系数和它对应的 ${\mathrm{\Psi }}_v$$\Psi_v$ 中的小波系数的距离不超过 $2ϵ$$2\epsilon$ 。

     考虑到我们使用经验特性函数来描述分布，因此这种分布的相似性就转换为embedding 的相似性。因此如果选择合适的 scale ，则结构上等价的节点具有 ϵ-structurally similar embedding 。

4. 结构相似节点的 embedding ：接着我们证明局部邻域结构相似的顶点具有相似的 embedding 。

   设顶点 $v$$v$ 的 $K$$K$ 阶领域为 ${\mathcal{N}}_K(v)$$\mathcal N_K(v)$ ， ${\tilde{\mathcal{N}}}_K(v)$$\tilde{\mathcal N}_K(v)$ 为顶点 $v$$v$ 的一个扰动的 $K$$K$ 阶邻域，这是通过对顶点 $v$$v$ 的原始 $K$$K$ 阶邻域重新调整边来得到。假设扰动后的图拉普拉斯矩阵为 $\tilde{\mathbf{L}}$$\tilde{\mathbf L}$ ，接下来我们证明：如果顶点邻域的扰动很小，则顶点的小波系数的变化也很小。

   假设扰动很小，即： $\mathrm{\forall }k\le K,||{\mathbf{L}}^k-{\tilde{\mathbf{L}}}^k|{|}_F\le ϵ$$\forall k\le K, ||\mathbf L^k-\tilde{\mathbf L}^k||_F\le \epsilon$ 。我们使用核 $g_s$$g_s$ 的 $K$$K$ 阶泰勒公式在零点展开来表示扰动图的小波系数：

   $$\tilde{\mathbf{\Psi }}=\sum _{k=0}^K{\alpha }_k{\tilde{\mathbf{L}}}^k+\tilde{\mathbf{U}}r(\tilde{\mathbf{\Lambda }}){\tilde{\mathbf{U}}}^{\mathrm{\top }}$$

   我们使用 Weyl 定理将图结构中的扰动与图拉普拉斯算子的特征值变化联系起来。特别地，图的小扰动导致特征值的小扰动。即，对于每个 $\tilde{\lambda }$$\tilde\lambda$， $r(\tilde{\lambda })$$r(\tilde \lambda)$ 和原始的 $r(\lambda )$$r(\lambda)$ 接近：

   $$r(\tilde{\lambda })=r(\lambda )+o(ϵ)\le Cϵ$$

   其中 $o(ϵ)$$o(\epsilon)$ 表示 $ϵ$$\epsilon$ 的一个无穷小量，$C$$C$ 为一个常数。

   综合所有因素，则有：

   $$\begin{array}{c}|{\mathrm{\Psi }}_{m,v}-{\tilde{\mathrm{\Psi }}}_{m,v}|\le |\sum _{k=0}^K{\alpha }_k({\mathbf{L}}^k-{\tilde{\mathbf{L}}}^k{)}_{m,v}|+{|\tilde{\mathbf{U}}r(\tilde{\mathbf{\Lambda }}){\tilde{\mathbf{U}}}^{\mathrm{\top }}|}_{m,v}+{|\mathbf{U}r(\mathbf{\Lambda }){\mathbf{U}}^{\mathrm{\top }}|}_{m,v}\\ =(\sum _{k=0}^K|{\alpha }_k|+1+C)ϵ\end{array}$$

   因此在GraphWave 中，结构相似的顶点具有相似的 embedding 。

1.1.4 scale 参数

1. 我们开发了一个自动的方法来为heat kernel $g_s$$g_s$ 中的 scale 参数 $s$$s$ 找到合适的取值范围，该方法将在 GraphWave 的多尺度版本中使用。

   我们通过分析热扩散 heat diffusion 小波的方差来指定 $s_{min}$$s_\min$ 和 $s_{max}$$s_\max$ 来作为区间边界。直观而言：

   • 较小的 $s$$s$ 值使得热传播的时间较短，从而使得热扩散的小波分布没有意义，因为此时只有很少的几个小波系数是非零，绝大多数小波系数都是零。

   • 较大的 $s$$s$ 值使得热传播的时间较长，热扩散的小波分布也没有意义，因为此时网络收敛到所有顶点都处于能量为 $1/N$$1/N$ 的同温状态。这意味着扩散分布diffusion distribution 与数据无关，因此没有信息。

   这里我们证明两个命题，从而为热扩散小波分布的方差和收敛速度提供洞察insight。然后我们使用这些结论来选择 $s_{min}$$s_\min$ 和 $s_{max}$$s_\max$ 。

2. 命题一：热扩散小波 ${\mathrm{\Psi }}_v(s)$$\Psi_v(s)$ 中非对角线的系数的方差与以下指标成正比：

   $$\text{VAR}\left[\{{\mathrm{\Psi }}_{m,v}^{(s)}\mid m\ne v\}\right]\propto {\mathrm{\Delta }}_v^{(0)}{\mathrm{\Delta }}_v^{(2s)}-{\left({\mathrm{\Delta }}_v^{(s)}\right)}^2$$

   其中 ${\mathrm{\Delta }}_v^{(s)}=|{\mathrm{\Psi }}_{v,v}^{(s)}-\frac{1}{N}|$$\Delta_v^{(s)} = |\Psi_{v,v}^{(s)} - \frac {1}{N}|$ 随着 $s$$s$ 的增加单调递减。这是因为 ${\mathrm{\Psi }}_{v,v}^{(s)}=\sum _{l=1}^N{e}^{-{\lambda }_{l}s}{U}_{v,l}^2$$\Psi_{v,v}^{(s)} = \sum_{l=1}^{N}e^{-\lambda_ls}U_{v,l}^2$ ，它随着 $s$$s$ 的增加单调递减。

   注意，${\mathrm{\Psi }}_{v,v}^{(0)}=1$$\Psi_{v,v}^{(0)} = 1$，因此 ${\mathrm{\Delta }}_v^{(0)}=|1-\frac{1}{N}|$$\Delta_v^{(0)} = |1 - \frac{1}{N}|$ 。

   证明：令小波 ${\mathrm{\Psi }}_v$$\Psi_v$ 的非对角线系数均值为 ${\tilde{\mu }}_v^{(s)}=\sum _{m\ne v}{\mathrm{\Psi }}_{m,v}^{(s)}/(N-1)$$\tilde\mu_v^{(s)} = \sum_{m\ne v} \Psi_{m,v}^{(s)}/(N-1)$ 。考虑到 ${\mathrm{\Psi }}_v$$\Psi_{v}$ 为一个概率分布，因此有 $\sum _{m\ne v}{\mathrm{\Psi }}_{m,v}^{(s)}=1-{\mathrm{\Psi }}_{v,v}^{(s)}$$\sum_{m\ne v}\Psi_{m,v}^{(s)} = 1-\Psi_{v,v}^{(s)}$ 。

   根据方差的定义有：

   $$\begin{array}{c}\text{VAR}\left[\{{\mathrm{\Psi }}_{m,v}^{(s)}\mid m\ne v\}\right]=\frac{1}{N-1}\sum _{m\ne v}{({\mathrm{\Psi }}_{m,v}^{(s)}-{\tilde{\mu }}_v^{(s)})}^2\\ =(\frac{1}{N-1}\sum _{m\ne v}({\mathrm{\Psi }}_{m,v}^{(s)}{)}^2)-{\left({\tilde{\mu }}_v^{(s)}\right)}^2\\ =\frac{N}{(N-1{)}^2}({\mathrm{\Psi }}_{v,v}^{(2s)}\frac{N-1}{N}-{\left({\mathrm{\Psi }}_{v,v}^{(s)}\right)}^2+\frac{2{\mathrm{\Psi }}_{v,v}^{(s)}}{N}-\frac{1}{N})\\ =\frac{N}{(N-1{)}^2}({\mathrm{\Delta }}_v^{(0)}{\mathrm{\Delta }}_v^{(2s)}-{\left({\mathrm{\Delta }}_v^{(s)}\right)}^2)\end{array}$$

3. 命题一证明了小波系数的方差是 ${\mathrm{\Delta }}_v^{(s)}$$\Delta_v^{(s)}$ 的函数，因此为了最大化方差我们必须分析 ${\mathrm{\Delta }}_v^{(s)}$$\Delta_v^{(s)}$ 。为了确保小波系数的分布具有足够大的容量（即分布的多样性足够大），我们需要最大化方差。

   因此我们选择区间 $[s_{min},s_{max}]$$[s_\min,s_\max]$ 来使得 ${\mathrm{\Delta }}_v(s)$$\Delta_v(s)$ 足够大，从而使得diffusion 既有足够长的时间来扩散、又不至于太长以至于到达网络的收敛状态（所有顶点的温度都相同）。

   注意，${\mathrm{\Delta }}_v(s)$$\Delta_v(s)$ “足够大”并不意味着最大化这个变量。

4. 命题二：热扩散小波系数 ${\mathrm{\Psi }}_{m,v}^{(s)}$$\Psi_{m,v}^{(s)}$ 的收敛上下界为：

   $$e^{-{\lambda }_N\lceil s\rceil }{\mathrm{\Delta }}_v^{(0)}\le {\mathrm{\Delta }}_v^{(s)}\le e^{{\lambda }_2\lfloor s\rfloor }{\mathrm{\Delta }}_v^{(0)}$$

   证明：对于非负的 $s$$s$ 有：

   $$\begin{array}{c}{\mathrm{\Delta }}_v^{(s+1)}=|{\mathrm{\Psi }}_{v,v}^{(s+1)}-\frac{1}{N}|=\left|\sum _{l=2}^N{e}^{-{\lambda }_l(s+1)}{U}_{v,l}^2\right|=|\sum _{l=2}^N{e}^{-{\lambda }_{l}s}{U}_{v,l}^2\times e^{-{\lambda }_l}|\\ \le e^{-{\lambda }_2}\left|\sum _{l=2}^N{e}^{-{\lambda }_{l}s}{U}_{v,l}^2\right|=e^{-{\lambda }_2}|{\mathrm{\Psi }}_{v,v}^{(s)}-\frac{1}{N}|=e^{-{\lambda }_2}{\mathrm{\Delta }}_v^{(s)}\end{array}$$

   第一个不等式是因为 $0={\lambda }_1<{\lambda }_2\le \cdots \le {\lambda }_N$$0=\lambda_1\lt\lambda_2\le\cdots\le\lambda_N$ ，因此 $e^{-{\lambda }_2}\ge \cdots \ge e^{-{\lambda }_N}$$e^{-\lambda_2}\ge \cdots\ge e^{-\lambda_N}$ 。这里用到了不变式：$|{\mathrm{\Psi }}_{v,v}^{(s)}-\frac{1}{N}|=\left|\sum _{l=2}^N{e}^{-{\lambda }_{l}s}{U}_{v,l}^2\right|$$\left|\Psi_{v,v}^{(s)} - \frac 1{N}\right| = \left|\sum_{l=2}^{N}e^{-\lambda_ls}U_{v,l}^2\right|$ 。

   对应的有：

   $${\mathrm{\Delta }}_v^{(s+1)}=|{\mathrm{\Psi }}_{v,v}^{(s+1)}-\frac{1}{N}|\ge e^{-{\lambda }_N}|{\mathrm{\Psi }}_{v,v}^{(s)}-\frac{1}{N}|=e^{-{\lambda }_N}{\mathrm{\Delta }}_v^{(s)}$$

   因此有：

   $$e^{-{\lambda }_N}\le \frac{{\mathrm{\Delta }}_v^{(s+1)}}{{\mathrm{\Delta }}_v^{(s)}}\le e^{-{\lambda }_2}$$

   对于任意的 $s\in \mathbb{N}$$s\in \mathbb N$ ，我们采用数学归纳法可以证明有：

   $$e^{-{\lambda }_{N}s}{\mathrm{\Delta }}_v^{(0)}\le {\mathrm{\Delta }}_v^{(s)}\le e^{-{\lambda }_{2}s}{\mathrm{\Delta }}_v^{(0)}$$

   由于 ${\mathrm{\Delta }}_v^{(s)}$$\Delta_v^{(s)}$ 是 $s$$s$ 的连续递增函数，因此我们选择大于等于零且满足条件的 $s$$s$ 进行向下、向上取整。

5. 选择 $s_{max}$$s_\max$：我们选择 $s_{max}$$s_\max$ 使得小波系数被局限在局部邻域上（即不能收敛到同温状态）。根据命题二：

   • 当大部分特征值倾向于 ${\lambda }_N$$\lambda_N$ 时，${\mathrm{\Delta }}_v^{(s)}$$\Delta_v^{(s)}$ 倾向于 $e^{-{\lambda }_{N}s}{\mathrm{\Delta }}_v^{(0)}$$e^{-\lambda_Ns}\Delta_v^{(0)}$ （命题二的下界）。

   • 当大部分特征值倾向于 ${\lambda }_2$$\lambda_2$ 时，${\mathrm{\Delta }}_v^{(s)}$$\Delta_v^{(s)}$ 倾向于 $e^{-{\lambda }_{2}s}{\mathrm{\Delta }}_v^{(0)}$$e^{-\lambda_2s}\Delta_v^{(0)}$ （命题二的上界）。

   如果 ${\mathrm{\Delta }}_v^{(s)}/{\mathrm{\Delta }}_v^{(0)}$$\Delta_v^{(s)}/\Delta_v^{(0)}$ 高于给定阈值 $\eta$$\eta$ （其中 $\eta <1$$\eta \lt 1$），则扩散是局部的。事实上这确保了 ${\mathrm{\Delta }}_v^{(s)}$$\Delta_v^{(s)}$ 最多收缩到其初始值 ${\mathrm{\Delta }}_v^{(0)}$$\Delta_v^{(0)}$的 $\eta \ast 100\mathrm{\%}$$\eta * 100\%$ （因为 ${\mathrm{\Delta }}_v^{(s)}$$\Delta_v^{(s)}$ 随着 $s$$s$ 的增加而单调递减 ），并产生如下形式的边界：

   $$\frac{{\mathrm{\Delta }}_v^{(s)}}{{\mathrm{\Delta }}_v^{(0)}}\ge \eta$$

   这个边界意味着 $e^{-\lambda s}\ge \eta$$e^{-\lambda s}\ge \eta$ 或者 $s\le -\log (\eta )/\lambda$$s\le -\log(\eta)/\lambda$ 。为了在两种收敛场景之间找到一个中间地带，我们将 $\lambda$$\lambda$ 设为 ${\lambda }_2$$\lambda_2$ 和 ${\lambda }_N$$\lambda_N$ 的几何平均值。与算术平均值相比，几何平均值在 $[{\lambda }_2,{\lambda }_N]$$[\lambda_2,\lambda_N]$ 范围内保持相等的权重，${\lambda }_2$$\lambda_2$ 中的 $ϵ\mathrm{\%}$$\epsilon\%$ 的变化与 ${\lambda }_N$$\lambda_N$ 的 $ϵ\mathrm{\%}$$\epsilon\%$ 的变化具有相同的效果。因此，我们选择 $s_{max}$$s_\max$ 为：

   $$s_{max}=-\frac{\log \eta }{\sqrt{{\lambda }_2{\lambda }_N}}$$

   其中 $0<\eta \le 1$$0\lt \eta\le 1$ 为超参数，$\eta$$\eta$ 越接近1 则$s_{max}$$s_{\max}$ 越小， $\eta$$\eta$ 越接近0 则 $s_{max}$$s_\max$ 越大。

6. 选择 $s_{min}$$s_\min$ ：我们选择 $s_{min}$$s_\min$ 使得每个小波都有足够长的时间来扩散，即限定：

   $$\frac{{\mathrm{\Delta }}_v^{(s)}}{{\mathrm{\Delta }}_v^{(0)}}\le \gamma$$

   $s_{max}$$s_\max$ 同样的分析我们有 $s\ge -\log (\gamma )/\lambda$$s\ge -\log(\gamma)/\lambda$。因此我们选择：

   $$s_{min}=-\frac{\log \gamma }{\sqrt{{\lambda }_2{\lambda }_N}}$$

   其中超参数 $1\ge \gamma \ge \eta >0$$1\ge \gamma \ge \eta\gt 0$ ，$\gamma$$\gamma$ 参数越接近1 则 $s_{min}$$s_{\min}$ 越小，$\gamma$$\gamma$ 参数越接近0 则则 $s_{min}$$s_\min$ 越大。

   为覆盖适当的 scale 区间，论文建议设置 $\eta =0.8$$\eta=0.8$ 以及 $\gamma =0.95$$\gamma = 0.95$ 。

1.2 实验

1. GraphWave 的 embedding 独立于下游任务，因此我们在不同任务中对其进行评估，从而证明它在捕获网络结构角色方面的潜力。

2. baseline 方法：我们将 GraphWave 和两个结构嵌入的 SOTA 基准方法 struc2vec、RolX 进行评估。

   • struc2vec：struc2vec 通过在 multilayer graph 上的一系列随机游走来发现不同尺度的结构嵌入。

   • RolX ：RolX 基于节点特征（如degree、三角形数量）的矩阵的非负矩阵分解的方法，该方法基于给定的一组潜在特征来描述每个节点。注意，GraphWave 和 struc2vec 在连续频谱上学习 embedding，而不是在离散的类别中学习。

   • 我们还将GraphWave 和最近的两种无监督节点 representation learning方法node2vec、Deepwalk 方法进行比较，以强调这些方法与我们基于结构相似性方法之间的差异。

   对于所有 baseline，我们使用这些模型的默认参数。对于 GraphWave 模型，我们使用多尺度版本，并设置 $d=50$$d=50$ ，以及使用 $[0,100]$$[0,100]$ 内均匀间隔的采样点 $t_i$$t_i$ 。

   我们再次注意到，graph embedding 方法（structure2vec、neural fingerprint、GCN 等等）不适用于这些 setting，因为它们嵌入了整个 graph，而我们嵌入了单个节点。

1.2.1 杠铃图

1. 我们首先考虑一个杠铃图。杠铃图由两个长链组成的稠密团构成，该图包含 8 个不同类别的结构等价节点，如图A 的颜色所示。我们通过PCA 可视化了不同模型学到的embedding ，相同的 embedding 具有相同的投影，这使得图 B~D 上的点发生重叠。

   • 从图D 可以看出， GraphWave 可以正确学习结构等价顶点的embedding，这为我们的理论提供了支撑（相同颜色的顶点几何完全重叠）。

   • 相反，struc2vec 和 RolX 都无法准确的识别结构等价性（相同颜色的节点并未重叠）。对于 struc2vec ，投影与预期的顺序不一致：黄色节点比红色节点离绿色节点更远。相比之下，RolX 产生高度相似的节点 embedding，其投影聚集成三个 high-level 的分组，这意味着 RolX 可以识别杠铃图中八个结构类别中的三个。

   • 所有方法都能识别杠铃图的稠密团的（紫色）的结构，但是只有GraphWave 能够准确识别杠铃图的链上节点的结构角色。

   

1.2.2 结构等价的图

1. 我们在人工合成的图上评估这些方法。我们开发了一个程序来生成合成图，这些合成图可以植入结构等价的子图，并且给出每个节点角色的真实标签。我们的目的是通过这些真实的角色标签来评估这些方法的性能。

   我们的合成图由不同类型的基础形状给出，这些形状类型包括 house,fan,star，它们沿着长度为 30 的圆环规则地放置。我们一共评估四种网络结构配置：

   • 在 house 配置中，我们选择将4 个 house 放置在一个长度为 30 的圆环上。

   • 在 varied 配置中，我们对每个类型的形状选择8 个，并随机放置在一个长度为 40 的圆环上，从而生成具有更丰富、更复杂结构角色的合成图。

   • 在 noise 配置中，我们随机添加边来增加扰动（最多 10% ），从而评估house perturbed, varied perturbed 的鲁棒性。

   我们对这四种网络结构 house, varied, house perturbed, varied perturbed 分别构造一个图，然后在这些构造的图上运行不同方法来得到节点 embedding 。

2. 我们通过两种 setting来评估每个embedding 算法的性能：

   • 无监督评估 setting：我们评估每种embedding 方法将具有相同结构角色的节点嵌入到一起的能力。我们使用 agglomerative 聚类算法（采用 single linkage ）来对每种方法学到的 embedding 进行聚类，然后通过以下指标来评估聚类质量：

     • 同质性 homogeneity：给定聚类结果的条件下，真实结构角色的条件熵。它评估聚类结果和真实结果的差异。

     • 完整性 completeness：在所有真实结构角色相等的节点中，有多少个被分配到同一个聚类。即评估聚类结果的准确性。

     • 轮廓系数 silhouette score ：它衡量簇内距离和簇间距离的关系。即评估样本聚类的合理性。

       对于样本 $v_i$$v_i$ ，假设它到同簇类其它样本的平均距离为 $a_i$$a_i$，则 $a_i$$a_i$ 越小说明该样本越应该被聚到本簇，因此定义 $a_i$$a_i$ 为簇内不相似度。假设它到其它簇 $C_j$$C_j$ 的平均距离为 $b_{i,j}$$b_{i,j}$ ，则定义簇间不相似度为 $b_j=\underset{j}{min}\{b_{i,j}\}$$b_j=\min_j\{b_{i,j}\}$ 。定义轮廓系数为：$s(i)=\frac{b(i)-a(i)}{max\{a(i),b(i)\}}$$s(i) = \frac{b(i) - a(i)}{\max\{a(i),b(i)\}}$ 。当 $s(i)$$s(i)$ 越接近 1 ，则说明样本 $v_i$$v_i$ 聚类合理；当 $s(i)$$s(i)$ 越接近 -1 ，则说明样本 $v_i$$v_i$ 聚类不合理。

   • 监督评估估 setting：我们将学到的节点 embedding 作为特征来执行节点分类，类别为节点的真实结构角色。我们使用kNN 模型，对所有样本进行10 折交叉验证。对于测试集的每个节点，我们根据它在训练集中最近邻的 4 个节点来预测该节点的结构角色，其中”近邻” 是通过 embedding 空间的距离来衡量。最终我们给出分类的准确率和 F1 得分作为评估指标。

   所有两种策略的每个实验都重复执行25 次，并报告评估指标的均值。

3. 模型embedding 的效果比较如下图所示。

   • 对于无监督和有监督的 setting ，GraphWave 都优于其它四种方法。

   • 所有实验中，node2vec、DeepWalk 的效果都很差，其得分显著低于基于结构等价的方法。这是因为这两个方法的重点都是学习节点的邻近关系，而不是节点的结构相似性。

   • GraphWave 的效果始终优于 struc2vec ，在每种 setting 下的指标都获得更高的得分。

   • 虽然 RolX 在部分实验中效果强于 GraphWave，但是 GraphWave 整体效果较好。

   • 轮廓系数silhouette score 表明：GraphWave 发现的簇往往更聚集并且簇之间的间隔更好。

   

4. 我们将GraphWave 学到的 embedding 进行可视化，这提供了一种观察节点之间结构角色差异的方法。

   如图 A 表示一个带 house 的环，图B 是它的 GraphWave 学到的 embedding 的 2 维PCA 投影。这证明了 GraphWave 可以准确区分不同结构角色的节点。

   图 C 给出了特性函数 ${\varphi }_v(t)=\frac{1}{N}\sum _{m=1}^N{e}^{it\times {\mathrm{\Psi }}_{v,m}}$$\phi_v(t) = \frac {1}{N} \sum_{m=1}^{N}e^{it\times \Psi_{v,m}}$ ，不同颜色对应不同结构角色的节点。其物理意义为：

   • 位于图外围的节点难以在图上扩散信号，因此派生出的小波具有很少的非零系数。因此这类节点的特性函数是一个较小的环状 2D 曲线。

   • 位于图核心（稠密区域）上的节点趋向于将信号扩散得更远，并在相同 $t$$t$ 值下到达更远的节点。因此这类节点的特性函数在 $x$$x$ 轴和 $y$$y$ 轴上具有更远的投影。

   

1.2.3 跨图的 Embedding 泛化

1. 我们分析embedding 如何识别位于不同图上的节点的结构相似性，这是为了评估embedding 能否识别跨图的结构相似性。

   我们通过以下过程来生成 200 个具有真实顶点结构角色标签的图。

   • 首先以 0.5 的概率来选择环形图或者链式图，从而确定了图的骨架。

   • 然后通过均匀随机选择环的大小或者链的长度来决定骨架的大小。

   • 最后随机选择一定数量的小图挂载到骨架上，这些小图以 0.5 的概率从 5 个节点的 house 或者 5 个节点的chain 中选取。

   为了在噪音环境中评估embedding 方法，我们还在节点之间随机添加10 个随机边，然后训练每个节点的 embedding 。接着用学到的 embedding 来预测每个节点的真实结构角色。

2. 为了评估每个方法在跨图上的泛化能力，我们使用10 折交叉验证，并且对于测试集中的节点我们选择训练集中和它最近邻（通过embedding 来计算距离）的4 个邻居节点来预测该测试节点的标签。注意：所选择的4 个邻居节点可能位于不同的图上。最后我们评估预测的准确率和 F1 得分，评估结果如下。结果表明：

   • GraphWave 方法在两个分类指标上均优于所有其它方法，这表明了 GraphWave 具有学习结构特征的能力，这种结构特征对于不同的图都有重要意义，且具有很高的预测能力。

   • 最近的无监督节点 representation learning 方法表现不佳，而表现第二好的方法是 RolX 。

   

1.2.4 可扩展性和鲁棒性

1. 这里我们分析 GraphWave 的可扩展性以及它对输入图中噪声的敏感性。

2. 为评估GraphWave 的可扩展性我们逐渐扩大了合成图的节点数量，我们给出了这些合成图上运行GraphWave 的时间和节点数量的关系，如下图所示。

   • GraphWave 的训练时间是边数量的线性函数，因此它是一种快速算法，可以使用稀疏矩阵表示 （sparse matrix representation ）来有效地实现。

   • GraphWave 的潜在瓶颈是通过经验特性函数将小波系数的分布转换成 embedding 向量。

     这里利用了小波系数的稀疏性。小波系数通常是稀疏的，因为GraphWave 通过合理的选择 scale 参数 $s$$s$ 使得小波不会被传播得太远。这种稀疏性可以降低embedding 过程的计算量，因为这里是一组稀疏矩阵相乘，并且在非零元素上应用 element-wise 函数。

   • 相比之下，struc2vec 无法应用到大图上，对于仅包含 100 个顶点的图，它都需要高达260 秒来学习顶点的 embedding 。而 RolX 可以扩展到类似大小的图上。

   

3. 接下来我们评估GraphWave 对噪音的鲁棒性。我们将噪音采取与 varied perturbed 相同的方式注入到图中，噪音水平由随机扰动的边占原始边的百分比给出。

   对于每个图，我们首先使用 GraphWave 学习节点embedding，然后使用 affinity propagation 聚类算法对embedding 进行聚类。最后我们根据节点的真实结构角色来评估聚类质量。注意，affinity propagation 算法不需要簇的数量作为输入，而是自动生成簇。这在实验中很重要，因为每个簇的含义可能受到 high level 的噪音而难以理解。

   除了同质性、完整性指标之外，我们还报告检测到的聚类的数量，从而衡量 GraphWave 发现的角色的丰富程度，我们随机运行10 次并报告平均结果。

   结果如下图所示。结果表明：即使存在强烈的噪音，GraphWave 的性能也是缓慢地降低。

   

1.2.5 真实数据集

1. 镜像 Karate 网络：我们首先考虑一个镜像 Karate 网络，并使用与 struc2vec 中相同的实验设置。镜像 Karate 网络是通过获取 karate 网络的两个副本，并添加给定数量的随机边而创建的。这些随机边中的每条边连接来自不同副本的镜像节点，代表 karate 俱乐部的同一个人，即镜像边 （mirrored edge ）。该实验的目标是通过捕获结构相似性来识别镜像节点。

   对于每个节点，我们基于节点embedding 利用 kNN 寻找结构最相似的节点，然后评估这些结构最相似节点中真实结构等价的比例。我们添加镜像边的数量从 1 到 25 不等，实验结果非常一致。GraphWave 的平均准确率为83.2%（最低为 75.2%、最高为 86.2%）、struc2vec 平均准确率为 52.5%（最低为 43.3%、最高为 59.4%）。此外，node2vec 和 DeepWalk 的准确率都不会高于 8.5%，因为它们是基于邻近性而不是结构相似性进行嵌入的。

2. 安然 email 网络：我们考虑对安然公司员工之间的电子邮件通信网络进行学习，由于公司存在组织架构，因此我们预期结构GraphWave 能够学到这种工作职位上的结构等价性。

   该网络中每个节点对应于安然的员工，边对应于员工之间的email 通信。员工的角色有七种，包括CEO、总裁（ president）、经理 （manager） 等。这些角色给出了网络节点的真实标签。我们用不同模型学习每个节点的 embedding，然后计算每两类员工之间的平均 L2 距离，结果如下所示。

   • GraphWave 捕获到了安然公司的复杂组织结构。如 CEO 和总裁在结构上与其它角色的距离都很远。这表明他们在电子邮件网络中的独特位置，这可以通过他们与其他人截然不同的局部连接模式来解释。另一方面，trader 交易员看起来离总裁很远、离董事director更近。

   • 相比之下，struc2vec 的结果不太成功，每个类别之间的距离几乎均匀分布。

   

   

3. 欧洲航空网络：接下来我们分析一系列航空公司网络，这些网络编码了不同航空公司运营的、机场之间的直飞航班。我们考虑六家在欧洲机场之间运营的航空公司：四家商业航空公司、两家货运航空公司。每家航空公司对应一个Graph，其中顶点表示机场/目的地、边表示机场之间的直飞航班。

   这里一共有 45 个机场，我们对其标记为枢纽机场（hub airport）、区域枢纽、商业枢纽、重点城市等几个类别，这些类别作为节点的真实结构角色。对每个Graph我们学习图中每个机场的 embedding，然后将来自不同Graph 的同一个机场的 embedding 进行拼接，然后使用 t-SNE 可视化。我们还将拼接后的 embedding 作为 agglomerative 聚类的输入，然后评估同质性、完整性、轮廓系数。

   我们衡量了每个簇中的机场与ground-truth 结构角色的对应程度（如上表所示）。从上表可以看到，GraphWave 在所有三个聚类指标上都优于替代方法。

   下图展示了机场 embedding 的 t-SNE 可视化。结果如下所示：

   • struc2vec 学习的 embedding 捕获了不同的航空公司，可以看到各航空公司的节点几乎各自聚在一起。这表明struc2vec 无法在不同的航空公司网络之间泛化，因此无法识别那些结构等价、但是不属于同一个航空公司的机场。

   • RolX 学到的 embedding 的 t-SNE 投影几乎没有任何明显的模式。

   • GraphWave 可以学到节点的结构等价性，即使这些节点位于不同的图上。这表明 GraphWave 能够学到针对真实世界网络有意义的结构嵌入。